#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>


// 全排列 + dijkstra
using namespace std;
using PII = pair<int, int>;

const int N = 8e4, M = 3e5 + 10;

int n, m;
int h[M], e[M], ne[M], w[M], idx;
int dist[6][N];
int plc[6];
bool state[N];
bool visited[6];
int res = 0x3f3f3f3f;

void add(int a, int b, int c){
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}

void dijkstra(int k){
    memset(state, 0, sizeof state);
    dist[k][plc[k]] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> que;
    que.push({0, plc[k]});

    while(que.size()){
        PII temp = que.top();
        que.pop();

        int ver = temp.second, dis = temp.first;
        if(state[ver]) continue;

        state[ver] = true;

        for (int u = h[ver]; u != -1; u = ne[u]){
            int j = e[u];
            if(dist[k][j] > dis + w[u]){
                dist[k][j] = dis + w[u];
                que.push({dist[k][j], j});
            }
        }
    }
}

void dfs(int now, int v, int num){
    if(num == 5){
        res = min(res, v);
        return;
    }

    for (int i = 1; i <= 5; i ++){
        if(!visited[i] && dist[now][plc[i]] != 0x3f3f3f3f){
            visited[i] = true;
            dfs(i, v + dist[now][plc[i]], num + 1);
            visited[i] = false;
        }
    }
}


void solve(){
    for (int i = 1; i <= 5; i ++){
        if(dist[0][plc[i]] != 0x3f3f3f3f){
            visited[i] = true;
            dfs(i, dist[0][plc[i]], 1);
            visited[i] = false;
        }
    }

}

void printsss(){
    for (int i = 0; i < 6; i ++){
        for (int j = 1; j <= n; j ++){
            cout << dist[i][j] << " ";
        }
        cout << endl;
    }
}

int main()
{
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    memset(h, -1, sizeof h);
    memset(dist, 0x3f, sizeof dist);

    scanf("%d%d", &n, &m);
    plc[0] = 1;
    scanf("%d%d%d%d%d", &plc[1], &plc[2], &plc[3], &plc[4], &plc[5]);

    for (int i = 0; i < m; i ++){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
    }

    for (int i = 0; i < 6; i ++){
        dijkstra(i);
    }

    printsss();
    solve();


    printf("%d", res);

    return 0;
}